home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
C/C++ Users Group Library 1996 July
/
C-C++ Users Group Library July 1996.iso
/
listings
/
v_10_01
/
1001075a
< prev
next >
Wrap
Text File
|
1991-11-20
|
6KB
|
219 lines
/*
* Traversal of multiple binary trees
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define BIGINT (~(1 << ((8*sizeof(int))-1))) /* maximum integer */
#define NNODES 25 /* the number of nodes per tree */
#define NTREES 10 /* the number of binary trees to traverse */
/* binary tree node definition */
typedef struct node {
struct node *left; /* left sub-tree */
struct node *right; /* right sub-tree */
int key; /* current node value */
} NODE;
/***********************************************************************
* the following section is the single threaded example
***********************************************************************/
#ifdef SINGLE_THREAD
/* stack frame definition */
typedef struct frame {
struct node *data; /* the node being stacked */
struct frame *next; /* the next stack entry */
} FRAME;
/* push a tree node onto the stack */
void Push(FRAME **stackp, NODE *treep) {
FRAME *temp;
assert(treep != NULL);
temp = malloc(sizeof(FRAME));
assert(temp != NULL);
temp->data = treep;
temp->next = *stackp;
(*stackp) = temp;
}
/* get the top data item from the stack (without popping) */
int Top(FRAME *stackp) {
NODE *temp;
assert(stackp != NULL);
temp = stackp->data;
return(temp->key);
}
/* print the lowest value of all N trees */
void DisplayLowest(FRAME *stackp[], int *lowest) {
int current;
int topvalue;
int temp=BIGINT;
int i;
/* for each tree in the list... */
for (i=0; i < NTREES; i++) {
/* if the tree has not been completely traversed, */
if (stackp[i] != NULL) {
/* get the current key of this tree */
topvalue = Top(stackp[i]);
/* compare the current key with the other trees */
if (topvalue < temp) {
/* save the current tree number and its key */
current = i;
temp = topvalue;
}
}
}
printf("key = %d\n", temp);
*lowest = current;
}
/* removes and returns the top entry from the stack */
NODE *Pop(FRAME **stackp) {
FRAME *temp;
NODE *data;
temp = *stackp;
*stackp = (*stackp)->next;
data = temp->data;
free(temp);
return(data);
}
/* traverse the right sub-tree */
void TraverseRightSub(FRAME **stackp) {
NODE *temp;
FRAME *sframe;
/* find the right sub-tree of the current node */
temp = Pop(stackp);
temp = temp->right;
/* traverse the sub tree as far left as possible */
while (temp != NULL) {
Push(stackp, temp);
temp = temp->left;
}
}
/* determine if there are unvisited nodes */
int StacksExist(FRAME *stackp[]) {
int i;
for (i = 0; i < NTREES; i++){
if (stackp[i] != NULL)
return(1);
}
return(0);
}
void MergeTrees(NODE *treep[]) {
FRAME *stackp[NTREES];
int i;
/* preload all stacks */
for (i = 0; i < NTREES; i++) {
stackp[i] = NULL;
while (treep[i] != NULL) {
Push(&stackp[i], treep[i]);
treep[i] = treep[i]->left;
}
}
do {
DisplayLowest(stackp, &i);
TraverseRightSub(&stackp[i]);
} while(StacksExist(stackp));
}
/***********************************************************************
* the following section is the multi threaded example
***********************************************************************/
#else
#include <multi_c.h>
/* print the contents of a node (wait until it is the lowest key) */
void PrintNode(NODE *tree) {
static int CurrentKey = BIGINT;
/* wait until this node contains the lowest key value */
do {
if (CurrentKey > tree->key)
CurrentKey = tree->key;
MtCYield();
} while (CurrentKey != tree->key);
/* reinitialize the current key */
CurrentKey = BIGINT;
printf("key = %d\n", tree->key);
}
/* recursively visit the nodes in a tree */
void PrintTree(NODE *tree) {
if (tree != NULL) {
PrintTree(tree->left);
PrintNode(tree);
PrintTree(tree->right);
}
}
/* traverse multiple binary trees */
void MergeTrees(NODE **trees) {
int i;
/* create a thread for each tree... */
for (i = 0; i < NTREES; i++) {
MtCCoroutine(PrintTree(&trees[i]));
}
}
#endif
/* recursively add a node to the tree */
void AddKey(NODE **treep, int key) {
if ((*treep) == NULL) {
(*treep) = malloc(sizeof(NODE));
assert(*treep != NULL);
(*treep)->left = NULL;
(*treep)->right = NULL;
(*treep)->key = key;
} else {
if (key < (*treep)->key) {
AddKey(&((*treep)->left), key);
} else {
AddKey(&((*treep)->right), key);
}
}
}
/* build a tree of NNODES random keys */
void BuildTree(NODE **treep) {
int i;
for (i = 0; i < NNODES; i++) {
AddKey(treep, rand());
}
}
void main() {
NODE *trees[NTREES];
int i;
/* randomly build the trees */
for (i = 0; i < NTREES; i++) {
trees[i] = NULL;
BuildTree(&trees[i]);
}
/* traverse the trees as a single tree */
MergeTrees(trees);
}